/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
  if(pf.open(indexname, mode)) return 1;

  char info[PageFile::PAGE_SIZE];
  if (pf.endPid() == 0)
  {
    rootPid = -1;
    treeHeight = 0;
    if (pf.write(0, info)) return 2;
  }
  else
  {
    if (pf.read(0, info)) return 2;
    rootPid = *((PageId *)info);
    treeHeight = *((int *)(info + sizeof(PageId)));
  } 
  return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    char info[PageFile::PAGE_SIZE];
    *((PageId *)info) = rootPid;
    *((int *)(info + sizeof(PageId))) = treeHeight;
    pf.write(0, info);
    return pf.close();
}

// helper function for INSERT
RC BTreeIndex::helpInsert(int key, const RecordId& rid, PageId pid, int height, int& num, PageId& pidNum)
{
  num = -1;
  // Base case
  if (height == treeHeight)
  {
    BTLeafNode leaf;
    leaf.read(pid, pf);
    if (leaf.insert(key, rid))
    {
      BTLeafNode newNode;
      if (leaf.insertAndSplit(key, rid, newNode, num)) return 1;
      pidNum = pf.endPid();
      newNode.setNextNodePtr(leaf.getNextNodePtr());
      leaf.setNextNodePtr(pidNum);
      if (newNode.write(pidNum, pf)) return 1;
    }
    if (leaf.write(pid, pf)) return 1;
  }
 
  else
  {
    BTNonLeafNode nonleaf;
    int eid;
    PageId childNode;
    nonleaf.read(pid, pf);
    nonleaf.locate(key, eid);
    nonleaf.readEntry(eid, childNode);
    helpInsert(key, rid, childNode, height + 1, num, pidNum);
    if (num > 0)
    {
      if (nonleaf.insert(num, pidNum))
      {
        int mid;
        BTNonLeafNode sibling;
        if (nonleaf.insertAndSplit(num, pidNum, sibling, mid)) return 1;
        num = mid;
        pidNum = pf.endPid();
        if (sibling.write(pidNum, pf)) return 1;
      }
      else num = -1;
      nonleaf.write(pid, pf);
    }
  }
  return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
  int num;
  PageId pidNum;

  if (treeHeight == 0)
  {
    BTLeafNode leaf;
    leaf.insert(key, rid);
    rootPid = pf.endPid();
    treeHeight = 1;
    leaf.write(rootPid, pf);
    return 0;
  }

  if (helpInsert(key, rid, rootPid, 1, num, pidNum))
    return 1;

  if (num > 0)
  {
    BTNonLeafNode newRoot;
    newRoot.initializeRoot(rootPid, num, pidNum);
    rootPid = pf.endPid();
    treeHeight++;
    newRoot.write(rootPid, pf);
  }
  return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
  PageId pid = rootPid;
  int k = 0;
  while (k < (treeHeight - 1))
  {
    int eid;
    BTNonLeafNode nonleaf;
    nonleaf.read(pid, pf);
    nonleaf.locate(searchKey, eid);
    nonleaf.readEntry(eid, pid);
    k++;
  }

  BTLeafNode leaf;
  leaf.read(pid, pf);
  cursor.pid = pid;
  leaf.locate(searchKey, cursor.eid);
  return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{

  BTLeafNode leaf;
  leaf.read(cursor.pid, pf);
  leaf.readEntry(cursor.eid, key, rid);

  if (cursor.pid <= 0 || cursor.pid >= pf.endPid()) return 1;
  cursor.eid++;
  if (cursor.eid >= leaf.getKeyCount())
  {
    cursor.pid = leaf.getNextNodePtr();
    cursor.eid = 0;
  }
  return 0;
}
